package _29_最小的k个数;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 题目描述
 * 输入n个整数，找出其中最小的K个数。
 * 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 */
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (input.length == 0 || input.length < k) {
            return res;
        }
        //构建大顶堆，如果比堆顶小，进堆并删除堆顶
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int i = 0;
        for (; i < k; i++) {
            pq.add(input[i]);
        }
        for (; i < input.length; i++) {
            if (input[i] < pq.peek()) {
                pq.poll();
                pq.add(input[i]);
            }
        }
        res = new ArrayList<>(pq);
        return res;

    }

    int Partition(int a[], int low, int high) {
        int tmp = a[low];
        int pivokey = a[low];
        while (low < high) {
            while (low < high && a[high] >= pivokey) --high;
            a[low] = a[high];
            while (low < high && a[low] <= pivokey) ++low;
            a[high] = a[low];
        }
        a[low] =tmp;
        return low;
    }

    int selectK(int a[], int start, int end, int k) {
        int index = 0;
        if (start < end) {
            index = Partition(a, start, end);
            if (index == k)//正好找到第k大的数
            {
                index = k;
            } else if (index < k)//还要从index的右边找k-index个数
            {
                index = selectK(a, index + 1, end, k - index);
            } else if (index > k)//k个数都在Index的左边
            {
                index = selectK(a, start, index - 1, k);
            }
        }
        return index;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int nums[] = {4, 5, 1, 6, 2, 7, 3, 8};
        //solution.GetLeastNumbers_Solution(nums, 4);
        solution.selectK(nums,0,nums.length-1,5);
        System.out.println();
    }
}
